#!/usr/bin/python
# -*- coding:utf-8 -*-
#二叉查找树排序
#@author: wklken@yeah.net

import sys
#中序遍历二叉查找树就可以得到排序结果

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None
        
    def search(self, x, current_node):
        while current_node:
            if x == current_node.data:
                return True
            elif x < current_node.data:
                if current_node.left:
                    current_node = current_node.left
                    return self.search(x, current_node)
                else:
                    return False
            else:
                if current_node.right:
                    current_node = current_node.right
                    return self.search(x, current_node)
                else:
                    return False
        return False
    def insert(self, x):
        node = Node(x)
        if not self.root:
            self.root = node
            return True
        current_node = self.root     
        while current_node:
            if x == current_node.data:
                return True
            elif x < current_node.data:
                if not current_node.left:
                    current_node.left = node
                    return True
                current_node = current_node.left
            else:
                if not current_node.right:
                    current_node.right = node
                    return True
                current_node = current_node.right
        return False
    def middleOrder(self, l, current_node):
        if not current_node:
            return
        if current_node.left:
            self.middleOrder(l, current_node.left)
        l.append(current_node.data)
        if current_node.right:
            self.middleOrder(l, current_node.right)
    
'''
tree.insert(10)
print tree.root.data
tree.insert(5)
print tree.root.left.data
tree.insert(12)
print tree.root.right.data
tree.insert(11)
print tree.root.right.left.data
tree.insert(13)
print tree.root.right.right.data

print "In list"
print tree.search(10, tree.root)
print tree.search(5, tree.root)  
print tree.search(11, tree.root)  
print tree.search(12, tree.root)  
print tree.search(13, tree.root)  
print "Not In list"
print tree.search(14, tree.root)    
print tree.search(15, tree.root)  
'''
tree = BinaryTree()
l = [8, 4, 3, 7, 6, 5, 2, 1]
result = []
print "ori", l
for i in l:
    tree.insert(i)
tree.middleOrder(result, tree.root)
print "result", result